﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.Struct
{
    /// <summary>
    /// 这里的BTree 意思是一个二叉树类
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BTree<T> where T : IComparable<T>
    {
        public TreeNode<T> Root
        {
            get;
            set;
        }
        public BTree(TreeNode<T> root)
        {
            Root = root;
        }
    }

    public class TreeNode<T> : IComparable<TreeNode<T>> where T : IComparable<T>
    {
        public BTree<T> Tree
        {
            get;
            set;
        }

        public T Data
        {
            get;
            set;
        }

        public TreeNode<T> Parent;

        public TreeNode<T> LeftNode;

        public TreeNode<T> RightNode;

        public TreeNode(T data)
        {
            Data = data;
        }

        public int CompareTo(TreeNode<T> other)
        {
            return this.Data.CompareTo(other.Data);
        }
    }

    /// <summary>
    /// 真正的B 树类
    /// </summary>
    public class RealBTree<T> where T:IComparable<T>
    {
        public RealBTree(RealBTreeNode<T> root)
        {
            this.Root = root;
            this.Size = root.Size;
        }

        public RealBTreeNode<T> Root
        {
            get;
            private set;
        }

        public int Size
        {
            get;
            private set;
        }

        public RealBTreeNode<T> B_Tree_Search(RealBTreeNode<T> node, T key)
        {
            int i = 0;
            while (i < node.KeyLength && key.CompareTo(node.Keys[i]) > 0)
            {
                i++;
            }

            if (i < node.KeyLength && key.CompareTo(node.Keys[i]) == 0)
            {
                node.SearchIndex = i;
                return node;
            }
            if (node.IsLeaf)
            {
                return null;
            }
            else
            {
                return B_Tree_Search(node.Child[i], key);
            }
        }

        protected void B_Tree_Split_Child(RealBTreeNode<T> nodeParent, int fullNodeIndex, RealBTreeNode<T> fullNode)
        {
            RealBTreeNode<T> newNode = new RealBTreeNode<T>(nodeParent.Size);
            newNode.IsLeaf = fullNode.IsLeaf;
            int minsize = fullNode.Size;
            newNode.KeyLength = minsize - 1;

            for (int i = 0; i < minsize -1 ; i++)
            {
                newNode.Keys[i] = fullNode.Keys[minsize + i];
            }

            if (!fullNode.IsLeaf)
            {
                for (int i = 0; i < minsize; i++)
                {
                    newNode.Child[i] = fullNode.Child[minsize + i];
                }
            }

            fullNode.KeyLength = minsize - 1;

            for (int j = nodeParent.KeyLength; j > fullNodeIndex; j--)
            {
                nodeParent.Child[j + 1] = nodeParent.Child[j];
            }
            nodeParent.Child[fullNodeIndex + 1] = newNode;

            for (int j = nodeParent.KeyLength; j > fullNodeIndex; j--)
            {
                nodeParent.Keys[j] = nodeParent.Keys[j - 1];
            }

            nodeParent.Keys[fullNodeIndex] = fullNode.Keys[minsize - 1];
            nodeParent.KeyLength++;

        }

        public void B_Tree_Del(RealBTreeNode<T> node, T key)
        {
            int index = 0;
            while (index < node.KeyLength && key.CompareTo(node.Keys[index]) > 0)
            {
                index++;
            }
            if (node.IsLeaf && key.CompareTo(node.Keys[index]) == 0)
            {
                for (int i = node.KeyLength - 1; i > index; i--)
                {
                    node.Keys[i - 1] = node.Keys[i];
                }
                node.KeyLength--;
            }
            else if (!node.IsLeaf)
            {
                if (key.CompareTo(node.Keys[index]) == 0)
                {
                    if (index - 1 >= 0 && node.Child[index - 1].KeyLength >= node.Size)
                    {
                        var preKey = node.Child[index - 1].GetPreKey(key);
                        B_Tree_Del(node.Child[index - 1], preKey);
                        node.Keys[index] = preKey;
                    }
                    else if (index < node.KeyLength && node.Child[index + 1].KeyLength >= this.Size)
                    {
                        var preKey = node.Child[index + 1].GetNexKey(key);
                        B_Tree_Del(node.Child[index + 1], preKey);
                        node.Keys[index] = preKey;
                    }
                    else
                    {
                        RealBTreeNode<T> n = null;
                        RealBTreeNode<T> ci = null;
                        if (index > 0)
                        {
                            n = node.Child[index - 1];
                            ci = node.Child[index];

                            for (int i = index; i < node.KeyLength - 1; i++)
                            {
                                node.Keys[i] = node.Keys[i + 1];
                            }

                            for (int i = index; i < node.KeyLength; i++)
                            {
                                node.Child[i] = node.Child[i + 1];
                            }
                            node.KeyLength--;
                            if (node.KeyLength == 0)
                            {
                                this.Root = n;
                            }

                            for (int i = 0; i < ci.KeyLength; i++)
                            {
                                n.Keys[n.KeyLength + i] = ci.Keys[i];
                            }

                            for (int i = 0; i <= ci.KeyLength; i++)
                            {
                                n.Child[n.KeyLength + i+1] = ci.Child[i];
                            }

                            n.KeyLength = n.KeyLength + ci.KeyLength;
                        }
                        else if (index < node.KeyLength)
                        {
                            n = node.Child[index + 1];
                            ci = node.Child[index];

                            for (int i = index; i < node.KeyLength - 1; i++)
                            {
                                node.Keys[i] = node.Keys[i + 1];
                            }

                            for (int i = index; i < node.KeyLength; i++)
                            {
                                node.Child[i] = node.Child[i + 1];
                            }
                            node.KeyLength--;
                            if (node.KeyLength == 0)
                            {
                                this.Root = n;
                            }
                            for (int i = 0; i < n.KeyLength; i++)
                            {
                                ci.Keys[n.KeyLength + i] = n.Keys[i];
                            }

                            for (int i = 0; i <= n.KeyLength; i++)
                            {
                                ci.Child[n.KeyLength + i +1] = n.Child[i];
                            }

                            ci.KeyLength = n.KeyLength + ci.KeyLength;
                        }
                    }
                }
                else
                {
                    var ci = node.Child[index];
                    if (node.Child[index].KeyLength == node.Size - 1)
                    {
                        RealBTreeNode<T> n = null;
                        
                        if (index >= 1 && node.Child[index - 1].KeyLength >= this.Size)
                        {
                            n = node.Child[index - 1];

                            var kp = n.Keys[n.KeyLength -1];
                            var cp = n.Child[n.KeyLength];
                            n.KeyLength--;

                            var nK = node.Keys[index];

                            node.Keys[index] = kp;

                            for (int i = 0; i <= ci.KeyLength; i++)
                            {
                                ci.Keys[i + 1] = ci.Keys[i];
                            }
                            ci.Keys[0] = nK;

                            for (int i = 0; i <= ci.KeyLength + 1; i++)
                            {
                                ci.Child[i + 1] = ci.Child[i];
                            }
                            ci.Child[0] = cp;
                        }
                        else if (index <= node.KeyLength -1 && node.Child[index + 1].KeyLength >= this.Size)
                        {
                            n = node.Child[index + 1];

                            var kp = n.Keys[0];
                            var cp = n.Child[0];

                            for (int i = 0; i < n.KeyLength - 1; i++)
                            {
                                n.Keys[i] = n.Keys[i + 1];
                            }

                            for (int i = 0; i < n.KeyLength; i++)
                            {
                                n.Child[i] = n.Child[i + 1];
                            }
                            n.KeyLength--;

                            var nK = node.Keys[index];

                            node.Keys[index] = kp;
                            ci.Keys[ci.KeyLength] = nK;
                            ci.KeyLength++;
                            ci.Child[ci.KeyLength] = cp;
                        }
                        else
                        {
                            if (index >= 1)
                            {
                                n = node.Child[index - 1];
                                ci = node.Child[index];

                                n.Keys[n.KeyLength] = node.Keys[index -1];
                                n.KeyLength++;

                                for (int i = index; i < node.KeyLength - 1; i++)
                                {
                                    node.Keys[i] = node.Keys[i + 1];
                                }

                                for (int i = index; i < node.KeyLength; i++)
                                {
                                    node.Child[i] = node.Child[i + 1];
                                }
                                node.KeyLength--;
                                if (node.KeyLength == 0)
                                {
                                    this.Root = n;
                                }

                                for (int i = 0; i < ci.KeyLength; i++)
                                {
                                    n.Keys[n.KeyLength + i] = ci.Keys[i];
                                }

                                for (int i = 0; i <= ci.KeyLength; i++)
                                {
                                    n.Child[n.KeyLength + i] = ci.Child[i];
                                }

                                n.KeyLength = n.KeyLength + ci.KeyLength;
                                B_Tree_Del(n, key);

                            }
                            else if (index < node.KeyLength-1)
                            {
                                n = node.Child[index + 1];
                                ci = node.Child[index];

                                ci.Keys[ci.KeyLength] = node.Keys[index];
                                ci.KeyLength++;

                                for (int i = index; i < node.KeyLength - 1; i++)
                                {
                                    node.Keys[i] = node.Keys[i + 1];
                                }

                                for (int i = index; i < node.KeyLength; i++)
                                {
                                    node.Child[i] = node.Child[i + 1];
                                }
                                node.KeyLength--;
                                if (node.KeyLength == 0)
                                {
                                    this.Root = n;
                                }
                                for (int i = 0; i < n.KeyLength; i++)
                                {
                                    ci.Keys[n.KeyLength + i] = n.Keys[i];
                                }

                                for (int i = 0; i <= n.KeyLength; i++)
                                {
                                    ci.Child[n.KeyLength + i] = n.Child[i];
                                }

                                ci.KeyLength = n.KeyLength + ci.KeyLength;
                                B_Tree_Del(ci, key);
                            }
                        }
                    }
                    B_Tree_Del(ci, key);
                }
            }
        }

        public void B_Tree_Insert(T key)
        {
            var root = this.Root;
            if (root.IsFull)
            {
                RealBTreeNode<T> s = new RealBTreeNode<T>(root.Size);
                this.Root = s;
                s.IsLeaf = false;
                s.KeyLength = 0;
                s.Child[0] = root;
                B_Tree_Split_Child(s, 0, root);
                B_Tree_Insert_NonFull(s, key);
            }
            else
            {
                B_Tree_Insert_NonFull(root, key);
            }
        }

        public void B_Tree_Insert_NonFull(RealBTreeNode<T> node, T key)
        {
            var index = node.KeyLength -1;
            if (node.IsLeaf)
            {
                while (index >= 0 && key.CompareTo(node.Keys[index]) < 0)
                {
                    node.Keys[index + 1] = node.Keys[index];
                    index--;
                }
                node.Keys[index + 1] = key;
                node.KeyLength++;
            }
            else
            {
                while (index >= 0 && key.CompareTo(node.Keys[index]) < 0)
                {
                    index--;
                }
                index++;
                if (node.Child[index].IsFull)
                {
                    B_Tree_Split_Child(node, index, node.Child[index]);
                    if(key.CompareTo(node.Keys[index])>0)
                    {
                        index++;
                    }
                }
                B_Tree_Insert_NonFull(node.Child[index], key);
            }
        }

        public static RealBTree<T> CreateRealBTree(int size)
        {
            RealBTreeNode<T> root = new RealBTreeNode<T>(size);
            root.IsLeaf = true;
            root.KeyLength = 0;
            return new RealBTree<T>(root);
        }
    }

    public class RealBTreeNode<T> where T: IComparable<T>
    {
        public T[] Keys
        {
            get;
            set;
        }
        public RealBTreeNode<T>[] Child
        {
            get;
            set;
        }
        public readonly int Size;
        public int KeyLength
        {
            get;
            set;
        }

        public int SearchIndex
        {
            get;
            set;
        }

        public T GetPreKey(T key)
        {
            if (this.IsLeaf)
            {
                return this.Keys[this.KeyLength - 1];
            }
            else
            {
                return this.Child[this.KeyLength].GetPreKey(key);
            }
        }

        public T GetNexKey(T key)
        {
            if (this.IsLeaf)
            {
                return this.Keys[0];
            }
            else
            {
                return this.Child[this.KeyLength].GetPreKey(key);
            }
        }

        public bool IsFull
        {
            get
            {
                return KeyLength == 2 * Size - 1;
            }
        }

        public RealBTreeNode(int size)
        {
            Keys = new T[2 * size - 1];
            Child = new RealBTreeNode<T>[2*size];
            this.Size = size;
            this.SearchIndex = -1;
        }

        public bool IsLeaf
        {
            get;
            set;
        }
    }
}
